package _interview100;

import java.util.Arrays;

/**
 * 322. 零钱兑换
 */
public class No322 {
    private int[] coins;

    /**
     * 1. 递归
     */
    public int coinChange1(int[] coins, int amount) {
        this.coins = coins;
        int ans = dfs(coins.length - 1, amount);
        return ans >= Integer.MAX_VALUE / 2 ? -1 : ans;
    }

    private int dfs(int i, int c) {
        if (i < 0) return c == 0 ? 0 : Integer.MAX_VALUE / 2;
        else if (coins[i] > c) return dfs(i - 1, c);
        else return Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
    }

    /**
     * 2. 迭代
     */
    public int coinChange2(int[] coins, int amount) {
        int n = coins.length;

        int[][] f = new int[n + 1][amount + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE / 2);
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c < amount + 1; c++) {
                if (coins[i] > c) f[i + 1][c] = f[i][c];
                else f[i + 1][c] = Math.min(f[i][c], f[i + 1][c - coins[i]] + 1);
            }
        }

        int ans = f[n][amount];
        return ans >= Integer.MAX_VALUE / 2 ? -1 : ans;
    }

    /**
     * 4. 空间优化：一个数组
     */
    public int coinChange4(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        Arrays.fill(f, Integer.MAX_VALUE / 2);
        f[0] = 0;
        for (int coin : coins) {
            for (int c = coin; c < amount + 1; c++) {
                f[c] = Math.min(f[c], f[c - coin] + 1);
            }
        }

        int ans = f[amount];
        return ans >= Integer.MAX_VALUE / 2 ? -1 : ans;
    }
}
